﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;

namespace SelecSort
{
	class Program
	{
		/// <summary>
		/// 直接选择排序时间复杂度：O(n^2)
		/// </summary>
		/// <param name="args"></param>
		static void Main(string[] args)
		{
			//2次比较
			for (int i = 1; i <= 5; i++)
			{
				List<int> list = new List<int>();
				//随机选择1000个数到数组中
				for (int j = 0; j < 500; j++)
				{
					Thread.Sleep(j);
					list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 10000));
				}
				Console.WriteLine("\n第" + i + "次比较：");
				Stopwatch watch = new Stopwatch();
				watch.Start();
				var result = list.OrderBy(single => single).ToList();
				watch.Stop();
				Console.WriteLine("\n快速排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", result.Take(10).ToList()));
				watch.Start();
				result = SelectSort(list);
				watch.Stop();
				Console.WriteLine("\n直接选择排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", result.Take(10).ToList()));
			}
			Console.ReadLine();
		}

		/// <summary>
		/// 直接选择排序
		/// </summary>
		/// <param name="list"></param>
		/// <returns></returns>
		public static List<int> SelectSort(List<int> list)
		{
			for (int i = 0; i < list.Count-1; i++)
			{
				//假设tempIndex的下标的值最小
				int tempIndex = i;
				for (int j = i+1; j < list.Count; j++)
				{
					//如果j下标的值小于tempIndex的值，则记录较小值的下标
					if (list[j] < list[tempIndex])
						tempIndex = j;
				}
				//最后将假设的最小值跟真的最小值进行交换
				int tempData = list[tempIndex];
				list[tempIndex] = list[i];
				list[i] = tempData;
			}
			return list;
		}
	}
}
